//20: 有效的括号
//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
//
// 有效字符串需满足：
//
//
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
//
//
//
//
// 示例 1：
//
//
//输入：s = "()"
//输出：true
//
//
// 示例 2：
//
//
//输入：s = "()[]{}"
//输出：true
//
//
// 示例 3：
//
//
//输入：s = "(]"
//输出：false
//
//
// 示例 4：
//
//
//输入：s = "([)]"
//输出：false
//
//
// 示例 5：
//
//
//输入：s = "{[]}"
//输出：true
//
//
//
// 提示：
//
//
// 1 <= s.length <= 10⁴
// s 仅由括号 '()[]{}' 组成
//
// Related Topics 栈 字符串 👍 3244 👎 0
//思路：1 创建一个栈。2遍历，左括号入栈，右括号跟栈顶匹配 3遍历完成栈为空则true


import java.util.Stack;

public class IsValid {
    public static void main(String[] args) {
        String s="{";
        System.out.println(isValid(s));
    }
    public static boolean isValid(String s) {
        String left="([{";
        String right=")]}";
        Stack<Character> stack=new Stack();
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if (left.contains(String.valueOf(c))){
             stack.push(c);
            }
            if (stack.isEmpty()){
                return false;
            }
            if (right.contains(String.valueOf(c))){
                char sc=  stack.pop();
                if ((sc=='('&&c==')')||(sc=='['&&c==']')||(sc=='{'&&c=='}')){
                    continue;
                }else {
                    return false;
                }
            }
        }
        if (stack.isEmpty()) {
            return true;
        }else {
            return false;
        }
    }
}
